import javax.xml.transform.Source;
import java.lang.invoke.MutableCallSite;
import java.util.Deque;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * @Description: 滑动窗口最大值
 * 给你一个整数数组 nums，
 * 有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。
 * 你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
 * 返回 滑动窗口中的最大值 。
 * @Date:Create in 14:58  2022/7/13
 */
public class maxSlidingWindow0239 {

    public static void main(String[] args) {
        int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
        int k = 3;
        int[] arr = maxSlidingWindow4(nums, k);
        for (int i : arr) {
            System.out.println(i);
        }
    }

    //暴力解法 超出时间限制
    public static int[] maxSlidingWindow1(int[] nums, int k) {
        int size1 = nums.length;
        int size2 = size1 - k + 1;
        int[] arr = new int[size2];

        for (int i = 0; i < size2; i++) {
            int temp = nums[i];
            for (int j = i; j < i + k; j++) {
                if (temp < nums[j]) temp = nums[j];
            }
            arr[i] = temp;
        }
        return arr;
    }

    //使用单调队列
    public static int[] maxSlidingWindow2(int[] nums, int k) {
        if (nums.length == 1) return nums;
        int len = nums.length - k + 1;
        int[] arr = new int[len];
        int num = 0;
        MyQueue myQueue = new MyQueue();
        for (int i = 0; i < k; i++) myQueue.add(nums[i]);

        arr[num++] = myQueue.peek();

        for (int i = k; i < nums.length; i++) {
            myQueue.poll(nums[i - k]);
            myQueue.add(nums[i]);
            arr[num++] = myQueue.peek();
        }
        return arr;
    }

    //使用单调队列2
    public static int[] maxSlidingWindow3(int[] nums, int k) {
        int n = nums.length;
        Deque<Integer> deque = new LinkedList<Integer>();
        for (int i = 0; i < k; ++i) {
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offerLast(i);
        }

        int[] ans = new int[n - k + 1];
        ans[0] = nums[deque.peekFirst()];
        for (int i = k; i < n; ++i) {
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offerLast(i);
            while (deque.peekFirst() <= i - k) {
                deque.pollFirst();
            }
            ans[i - k + 1] = nums[deque.peekFirst()];
        }
        return ans;
    }


    //使用优先队列（堆）
    public static int[] maxSlidingWindow4(int[] nums, int k) {
        int n = nums.length;
        //这里我们传入了一个比较器，当两者的值相同时，比较下标的位置，下标大的在前面。
        PriorityQueue<int[]> queue = new PriorityQueue<>((p1, p2) -> p1[0] != p2[0] ? p2[0] - p1[0] : p2[1] - p1[1]);
        //初始化前K的元素到堆中
        for (int i = 0; i < k; i++) {
            queue.offer(new int[]{nums[i], i});
        }
        //有n-k+1个
        int[] ans = new int[n - k + 1];
        //将第一次答案加入数据
        ans[0] = queue.peek()[0];

        for (int i = k; i < n; i++) {
            //将新元素加入优先队列
            queue.offer(new int[]{nums[i], i});
            //循环判断当前队首是否在窗口中，窗口的左边界为i-k
            while (queue.peek()[1] <= i - k) {
                queue.poll();
            }
            //在窗口中直接赋值即可
            ans[i - k + 1] = queue.peek()[0];
        }
        return ans;
    }
}


class MyQueue {
    Deque<Integer> deque = new LinkedList<>();

    //弹出元素时，比较当前要弹出的数值是否等于队列出口的数值，如果相等则弹出
    //同时判断队列当前是否为空
    void poll(int val) {
        if (!deque.isEmpty() && val == deque.peek()) {
            deque.poll();
        }
    }

    //添加元素时，如果要添加的元素大于入口处的元素，就将入口元素弹出
    //保证队列元素单调递减
    //比如此时队列元素3,1，2将要入队，比1大，所以1弹出，此时队列：3,2
    void add(int val) {
        while (!deque.isEmpty() && val > deque.getLast()) {
            deque.removeLast();
        }
        deque.add(val);
    }

    //队列队顶元素始终为最大值
    int peek() {
        return deque.peek();
    }

}
